#include "undigraph.h"
#include "chain_table.h"

#include <vector>
using std::vector;

#include <queue>
using std::queue;

#include <iostream>
using std::cout;
using std::endl;

#include "min_heap.h"

// vertex

vertex::vertex(int num) : m_number(num)
{
}

bool vertex::operator==(const vertex &x)
{
    return m_number == x.m_number;
}

bool vertex::operator!=(const vertex &x)
{
    return !(*this == x);
}

bool vertex::operator<(const vertex &x)
{
    return m_number < x.m_number;
}

bool vertex::operator<=(const vertex &x)
{
    return ((*this < x) || (*this == x));
}

bool vertex::operator>(const vertex &x)
{
    return !(*this <= x);
}

bool vertex::operator>=(const vertex &x)
{
    return !(*this < x);
}

// ------------------------------------------------------------------------------------------------

// ------------------------------------------------------------------------------------------------
// undigraph

// 初始化, 默认是一个空图. 零图
undigraph::undigraph(int vertex_count)
    : m_adjacency_linked_list(vertex_count + 1), m_vertex_count(vertex_count), m_edge_count(0)
{
    for (int i = 1; i <= m_vertex_count; ++i)
    {
        chain_table_node<vertex> *x = m_adjacency_linked_list[i].gethead();
        x->m_data = vertex(i);
    }
}

// 添加一条边 (a, b)
void undigraph::insert(int a, int b)
{
    // 检查操作的合法性
    if (a == b)
    {
        // 无向图中不能有自连边
        return;
    }

    if (isexist_edge(a, b))
    {
        // 在无向图中, 任意两个不相同的顶点之间至多有一条边
        return;
    }

    m_adjacency_linked_list[a].insert_ascending(vertex(b));
    m_adjacency_linked_list[b].insert_ascending(vertex(a));
    ++m_edge_count;
}

// 判断无向边(a, b)是否存在, 存在返回true, 不存在返回false
bool undigraph::isexist_edge(int a, int b)
{
    chain_table_node<vertex> *res = m_adjacency_linked_list[a].find(vertex(b));
    if (res == nullptr)
    {
        return false;
    }
    else
    {
        return true;
    }
}

// 删除一条边 (a, b)
void undigraph::erase(int a, int b)
{
    if (a == b)
    {
        return;
    }

    if (!isexist_edge(a, b))
    {
        return;
    }

    // 即删除链表的节点 by vertex
    m_adjacency_linked_list[a].erase(vertex(b));
    m_adjacency_linked_list[b].erase(vertex(a));
    --m_edge_count;
}

/*
    广度优先搜索bfs, 确定一个顶点的可达的顶点集, 可达顶点集包含它本身
    @v: 字典序最小的bfs顶点访问序列
*/
void undigraph::BFS(int num, vector<int> &v)
{
    vector<bool> sign(m_vertex_count + 1, false);
    BFS(num, v, sign);
}

// 广度优先搜索bfs, 确定一个顶点的可达的顶点集, 可达顶点集包含它本身
void undigraph::BFS(int num, vector<int> &v, vector<bool> &sign)
{
    if (m_vertex_count == 0)
    {
        // 如果是一个空图
        return;
    }

    if (sign.size() < m_vertex_count + 1)
    {
        // 非法条件, 无法计算
        return;
    }

    // 不需要
    // if (sign[num] == true)
    // {
    //     // 已经对其进行了标记, 说明这是在确定连通分支
    //     return;
    // }

    queue<chain_table_node<vertex> *> q; // 其中pop必是赋值, 而不是先析构, 再载入一个新的
    // vector<bool> sign(m_vertex_count + 1, false);

    // 载入初始条件
    chain_table_node<vertex> *cur = m_adjacency_linked_list[num].gethead();
    q.push(cur);
    sign[cur->m_data.m_number] = true; // 已经被触及的标记为true
    // 展开过程
    while (!q.empty())
    {
        cur = q.front();
        v.push_back(cur->m_data.m_number);
        q.pop();

        // 展开
        cur = cur->m_next;
        while (cur != nullptr)
        {
            if (sign[cur->m_data.m_number] == false)
            {
                // 没有被触及的, 将要被触及
                chain_table_node<vertex> *tmp = m_adjacency_linked_list[cur->m_data.m_number].gethead();
                q.push(tmp); // 只有tmp才有展开的能力
                sign[cur->m_data.m_number] = true;
            }
            cur = cur->m_next;
        }
    }
}

// 深度优先搜索dfs, 确定一个顶点的可达的顶点集, 可达顶点集包含它本身
void undigraph::DFS(int num, vector<int> &v)
{
    // 为了避免使用全局的标记数组, 我能想到的办法就只有再封装一层了
    vector<bool> sign(m_vertex_count + 1, false);
    DFS(num, v, sign);
}

/*
    深度优先搜索dfs, 确定一个顶点的可达的顶点集, 可达顶点集包含它本身
    @v: 字典序最小的dfs顶点访问序列, 传一个空vector
    @sign: 大小必须为m_vertex_count+1
*/
void undigraph::DFS(int num, vector<int> &v, vector<bool> &sign)
{
    chain_table_node<vertex> *cur = m_adjacency_linked_list[num].gethead();
    v.push_back(cur->m_data.m_number);
    sign[cur->m_data.m_number] = true;

    // 递归展开
    cur = cur->m_next;
    while (cur != nullptr)
    {
        if (sign[cur->m_data.m_number] == false)
        {
            DFS(cur->m_data.m_number, v, sign);
        }

        cur = cur->m_next;
    }
}

/*
    得到所有的连通分支
    @res: 中的每一个数组记录了一个连通分支的所有顶点数, 传一个空的vector<vector<int>>
*/
void undigraph::get_all_connected_components(vector<vector<int>> &res)
{
    vector<bool> sign(m_vertex_count + 1, false);
    int j = 0;
    for (int i = 1; i <= m_vertex_count; ++i)
    {
        if (sign[i] != true)
        {
            res.push_back(vector<int>(0));
            BFS(i, res[j], sign);
            ++j;
        }
    }
}

int get_minval(vector<int> &v)
{
    int sz = v.size();
    int minval = v[0];
    for (int i = 1; i < sz; ++i)
    {
        if (v[i] < minval)
        {
            minval = v[i];
        }
    }

    return minval;
}

// 为了应付题目要求所写的特定的有关连通分支的函数
void undigraph::connected_components_info(int &res_num, vector<int> &res_min_sequence)
{
    vector<vector<int>> connected_components;
    get_all_connected_components(connected_components);
    res_num = connected_components.size();

    for (int i = 0; i < res_num; ++i)
    {
        res_min_sequence.push_back(get_minval(connected_components[i]));
    }
}

/*
    最短路径, 使用Dijkstra
    存在最短路径, 返回长度; 不存在, 返回-1
*/
int undigraph::shortest_path_Dijkstra(int s, int d)
{
    vector<bool> visited(m_vertex_count + 1, false);
    vector<int> distance(m_vertex_count + 1, -1);
    vector<int> prev(m_vertex_count + 1, -1);
    single_source_shortest_paths(s, visited, distance, prev);

    return distance[d];
}

struct DJ_node
{
    chain_table_node<vertex>* m_self;
    int* m_distance;

    DJ_node(chain_table_node<vertex>* self = nullptr, int* distance = nullptr)
        : m_self(self)
        , m_distance(distance)
    {

    }

     // 比较
    bool operator==(const DJ_node&x)
    {
        return *m_distance == *(x.m_distance);
    }
    bool operator!=(const DJ_node&x)
    {
        return !(*this == x);
    }
    bool operator<(const DJ_node&x)
    {
        return *m_distance < *(x.m_distance);
    }
    bool operator<=(const DJ_node&x)
    {
        return *this == x || *this < x;
    }
    bool operator>(const DJ_node&x)
    {
        return !(*this <= x);
    }
    bool operator>=(const DJ_node&x)
    {
        return !(*this < x);
    }
};

/*
    Dijkstra算法
    在调用这个函数时, 先把这三个数组进行初始化, 再传参
    @visited 全初始化成false, 大小为vertex_count + 1
    @distance 全初始化成-1, 表示未知, 大小为vertex_count + 1
    @prev 全初始化成-1, 表示未知, 大小为vertex_count + 1
*/
void undigraph::single_source_shortest_paths(int start, vector<bool> &visited, vector<int> &distance, vector<int> &prev)
{
    // 一些检查过程

    // 载入初始条件
    vector<bool> sign(m_vertex_count + 1, false); // 表识是否已知, 即是否被放入到小根堆中过
    distance[start] = 0;
    min_heap<DJ_node> h;
    h.push({m_adjacency_linked_list[start].gethead(), &distance[start]}); // push一定要是该节点的本体节点
    sign[start] = true;

    // 计算过程
    while (!h.empty())
    {
        DJ_node cur = h.top();
        visited[cur.m_self->m_data.m_number] = true;
        h.pop();

        chain_table_node<vertex>* adjacency_node = cur.m_self->m_next;
        int ad_node_num = 0;
        int cur_num = cur.m_self->m_data.m_number;
        while (adjacency_node != nullptr)
        {
            ad_node_num = adjacency_node->m_data.m_number;
            if (visited[ad_node_num] == false)
            {
                // 如果还没有找到最短路径, 检查是否需要更新
                if (distance[ad_node_num] == -1 || distance[ad_node_num] > *cur.m_distance + 1)
                {
                    distance[ad_node_num] = *cur.m_distance + 1;
                    prev[ad_node_num] = cur_num;
                }
                if (sign[ad_node_num] == false)
                {
                    // 检查是否需要放入小根堆, 有可能已经放入到小根堆中了
                    h.push({m_adjacency_linked_list[ad_node_num].gethead(), &distance[ad_node_num]});
                    sign[ad_node_num] = true;
                }
                
            }

            adjacency_node = adjacency_node->m_next;
        }

    }
}
